package leetcode.templates.tarjan;

import java.util.ArrayList;
import java.util.List;

import leetcode.IDebug;
import leetcode.helper.H;

//执行用时：75 ms, 在所有 Java 提交中击败了83.90%的用户
//
//内存消耗：100.8 MB, 在所有 Java 提交中击败了95.76%的用户
//
//通过测试用例：17 / 17
public class Solution1192 implements IDebug {

	int id;
	int[] ids;
	int[] minid;
	int[] stack; // >> Stack<Integer> stack;
	int ps;
	int[] group;
	int groupid;
	List<List<Integer>> nexts;// >> List<Integer>[] >> Set<Integer>[]

	public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
		// 构图
		nexts = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			nexts.add(new ArrayList<>());
		}
		for (List<Integer> list : connections) {
			int a = list.get(0), b = list.get(1);
			nexts.get(a).add(b);
			nexts.get(b).add(a);
		}
		// 构建DAG
		id = 0;
		ids = new int[n];
		minid = new int[n];
		group = new int[n];
		groupid = 0;
		stack = new int[n];
		ps = 0;
		for (int i = 0; i < n; i++) {
			if (ids[i] == 0) {
				dfs(i, -1);
			}
		}
		// 收集答案
		List<List<Integer>> ans = new ArrayList<>();
		for (List<Integer> list : connections) {
			int a = list.get(0), b = list.get(1);
			if (group[a] != group[b]) {
				ans.add(list);
			}
		}
		return ans;
	}

	private void dfs(int i, int from) {
		minid[i] = ids[i] = ++id;
		stack[ps++] = i;
		List<Integer> next = nexts.get(i);
		for (int nxt : next) {
			if (from == nxt) {
				continue;
			}
			if (ids[nxt] == 0) {
				dfs(nxt, i);
			}
			if (group[nxt] == 0) {
				minid[i] = Math.min(minid[i], minid[nxt]);
			}
		}
		if (minid[i] == ids[i]) {
			group[i] = ++groupid;
			while (ps > 0 && stack[ps - 1] != i) {
				group[stack[--ps]] = groupid;
			}
			ps--;
		}
	}

	@Override
	public void debug4() {
		this.criticalConnections(4, H.str2intlist1("[[0,1],[1,2],[2,0],[1,3]]"));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution1192 so = new Solution1192();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
